package org.hot100_1;

public class leetcode84 {
//    public boolean canPartition(int[] nums) {
//
//        int sum =0;
//
//        for (int num:nums) {
//            sum=sum+num;
//        }
//
//        if (sum%2!=0){
//            return false;
//        }
//        int target = sum/2;
//        //dp[i]表示容量为i时，用nums中的数字进行填充的最大值。如nums={1，2，3，10}，dp[7]=6,
//        int [] dp = new int[target+1];
//        dp[0]=0;
//
//        //0/1背包问题,先遍历物品在遍历背包
//        for (int i = 0; i < nums.length; i++) {
//            //因为是0/1背包，所以要从target开始递减
//            for (int j = target; j >=nums[i]; j--) {
//                //dp[j]表示没有选择当前的数值nums[i],是上一次遍历的结果
//                //dp[j-nums[i]]+nums[i]表示选择了当前的数值nums[i]，因为nums[i]即表示重量也表示价值
//                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
//            }
//        }
//        return dp[target]==target;
//    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num:nums) {
            sum = sum+num;
        }
        if (sum%2!=0){
            return false;
        }
        int target = sum/2;
        int [] dp = new int[target+1];
        dp[0]=0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >=nums[i]; j--) {
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }

        return dp[target]==target;

    }
}
